/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function (board) {
  let m = board.length
  let n = board[0].length
  let dummy = m * n
  let uf = new UnionFind(m * n + 1) // 生成并查集
  for (let i = 0; i < m; i++) {
    if (board[i][0] === 'O') {
      uf.union(n * i + 0, dummy)
    }
    if (board[i][n - 1] === 'O') {
      uf.union(n * i + n - 1, dummy)
    }
  }
  for (let i = 0; i < n; i++) {
    if (board[0][i] === 'O') {
      uf.union(n * 0 + i, dummy)
    }
    if (board[m - 1][i] === 'O') {
      uf.union((m - 1) * n + i, dummy)
    }
  }
  let dirs = [[1, 0], [-1, 0], [0, -1], [0, 1]]
  for (let i = 1; i < m - 1; i++) {
    for (let j = 1; j < n - 1; j++) {
      if (board[i][j] === 'O') {
        for (let [di, dj] of dirs) {
          let ni = i + di
          let nj = j + dj
          if (board[ni][nj] == 'O') {
            uf.union(i * n + j, ni * n + nj)
          }
        }
      }
    }
  }
  for (let i = 1; i < m - 1; i++) {
    for (let j = 1; j < n - 1; j++) {
      if (!uf.connected(i * n + j, dummy)) {
        board[i][j] = 'X'
      }
    }
  }
  return board
};
class UnionFind {
  constructor(n) {
    this.count = n
    this.parent = new Array(n)
    for (let i = 0; i < n; i++) {
      this.parent[i] = i
    }
  }
  union (p, q) {
    let rootP = this.find(p)
    let rootQ = this.find(q)
    if (rootP === rootQ) {
      return
    }
    this.parent[rootP] = rootQ
    this.count--
  }
  connected (p, q) {
    let rootP = this.find(p)
    let rootQ = this.find(q)
    return rootP === rootQ
  }
  find (x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x])
    }
    return this.parent[x]
  }
  getCount () {
    return this.count
  }
}
let board = [["X", "X", "X", "X"], ["X", "O", "O", "X"], ["X", "X", "O", "X"], ["X", "O", "X", "X"]]
console.log(solve(board));